home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CTOOLS10.ARJ / HASH.C < prev    next >
C/C++ Source or Header  |  1991-12-31  |  10KB  |  339 lines

  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: hash.c $
  7. * Version:        $Revision: 1.4 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Module to implement generic hash tables.
  13. *
  14. * $Id: hash.c 1.4 91/12/31 19:40:02 kjb Exp $
  15. *
  16. * Revision History:
  17. * -----------------
  18. *
  19. * $Log:    hash.c $
  20. * Revision 1.4  91/12/31  19:40:02  kjb
  21. * Modified include file directories.
  22. * Revision 1.3  91/09/03  18:28:01  ROOT_DOS
  23. * Ported to UNIX.
  24. * Revision 1.2  91/09/01  16:43:56  ROOT_DOS
  25. * Minor cosmetic changes.
  26. * Added function hsh_kill() to delete a hash table and all the symbols it
  27. * contains.
  28. * Revision 1.1  91/08/16  13:14:45  ROOT_DOS
  29. * Initial revision
  30. ****************************************************************************/
  31.  
  32. #include <stdio.h>
  33. #include <malloc.h>
  34. #include <ctype.h>
  35. #include <signal.h>
  36. #include <string.h>
  37. #include "debug.h"
  38. #include "hash.h"
  39. #include "ssort.h"
  40.  
  41. PUBLIC void *hsh_newsym(int size)
  42. /****************************************************************************
  43. *
  44. * Function:        hsh_newsym
  45. * Parameters:    size    - Amount of memory to allocate for symbol
  46. * Returns:        Pointer to the allocated symbols user space.
  47. *
  48. * Description:    Allocates the memory required for a symbol, adding a small
  49. *                header at the start of the symbol. We return a reference to
  50. *                the user space of the symbol, as if it had be allocated via
  51. *                malloc.
  52. *
  53. ****************************************************************************/
  54. {
  55.     HSH_BUCKET    *sym;
  56.  
  57.     if ( !(sym = (HSH_BUCKET*)malloc(size+sizeof(HSH_BUCKET))) ) {
  58.         fprintf(stderr,"Can't get memory for BUCKET\n");
  59.         raise(SIGABRT);
  60.         return NULL;
  61.         }
  62.  
  63.     return HSH_USERSPACE(sym);        /* Return pointer to user space        */
  64. }
  65.  
  66. PUBLIC void hsh_freesym(void *sym)
  67. /****************************************************************************
  68. *
  69. * Function:        hsh_freesym
  70. * Parameters:    sym        - Symbol to free
  71. *
  72. * Description:    Frees a symbol previously allocated with newsym().
  73. *
  74. ****************************************************************************/
  75. {
  76.     free(HSH_HEADER(sym));
  77. }
  78.  
  79. PUBLIC HASH_TAB *hsh_init(unsigned maxsym,unsigned (*hash_function)(),
  80.                          int (*cmp_function)() )
  81. /****************************************************************************
  82. *
  83. * Function:        hsh_init
  84. * Parameters:    maxsym            - Maximum number of symbols
  85. *                hash_function    - Hash function to the table
  86. *                cmp_function    - Comparison function for the elements
  87. * Returns:        Pointer to the newly created hash table.
  88. *
  89. * Description:    Makes a hash table of the given size and returns a pointer
  90. *                to it. Note that we call calloc() to allocate the memory,
  91. *                so that all the hash table pointers are initially NULL.
  92. *
  93. ****************************************************************************/
  94. {
  95.     HASH_TAB    *p;
  96.  
  97.     if (!maxsym)
  98.         maxsym = 127;            /* Default size */
  99.  
  100.                         /*    |<--- space for table -->|<- and header -->| */
  101.     if( (p=(HASH_TAB*)calloc(1,(maxsym*sizeof(HSH_BUCKET*)) + sizeof(HASH_TAB)))
  102.             != NULL) {
  103.         p->size = maxsym;
  104.         p->numsyms = 0;
  105.         p->hash = hash_function;
  106.         p->cmp = cmp_function;
  107.         }
  108.     else {
  109.         fprintf(stderr,"Insufficient memory for symbol table\n");
  110.         raise(SIGABRT);
  111.         return NULL;
  112.         }
  113.     return p;
  114. }
  115.  
  116. PUBLIC void hsh_kill(HASH_TAB *tabp,void (*freeSym)(void *))
  117. /****************************************************************************
  118. *
  119. * Function:        hsh_kill
  120. * Parameters:    tabp    - Hash table to kill
  121. *                freeSym    - Pointer to user function to free a symbol
  122. *
  123. * Description:    Kills the hash table tab, by deleting all the symbols in the
  124. *                table, and then deleting the table itself. Note that we call
  125. *                the user supplied routine (*freeSym)() to free each hash
  126. *                table symbol. This allows the user program to perform any
  127. *                extra processing needed to kill each symbol (if each symbol
  128. *                contains pointers to other items on the heap for example).
  129. *                If no extra processing is required, just pass the address of
  130. *                hsh_freesym(), ie:
  131. *
  132. *                    hsh_kill(mytab,hsh_freesym);
  133. *
  134. ****************************************************************************/
  135. {
  136.     HSH_BUCKET    *p,*sym,**symtab;
  137.     int            i;
  138.  
  139.     if (tabp && tabp->size != 0)
  140.         for (symtab = tabp->table, i = tabp->size; --i >= 0 ; symtab++) {
  141.             sym = *symtab;
  142.             while (sym) {
  143.                 p = sym;
  144.                 sym = sym->next;
  145.                 (*freeSym)(HSH_USERSPACE(p));
  146.                 }
  147.             }
  148.     free(tabp);
  149. }
  150.  
  151. PUBLIC void *hsh_addsym(HASH_TAB *tabp, void *isym)
  152. /****************************************************************************
  153. *
  154. * Function:        hsh_addsym
  155. * Parameters:    tabp    - The hash table
  156. *                isym    - Symbol to add
  157. *
  158. * Description:    Adds a symbol to the hash table. The new symbol is linked
  159. *                onto the head of the chain at it's particular hash location.
  160. *
  161. ****************************************************************************/
  162. {
  163.     HSH_BUCKET    **p,*tmp;
  164.     HSH_BUCKET    *sym = HSH_HEADER(isym);
  165.  
  166.     p = &(tabp->table)[ (*tabp->hash)(isym) % tabp->size ];
  167.  
  168.     tmp = *p;
  169.     *p = sym;
  170.     sym->prev = p;
  171.     sym->next = tmp;
  172.  
  173.     if (tmp)
  174.         tmp->prev = &sym->next;
  175.  
  176.     tabp->numsyms++;
  177.     return HSH_USERSPACE(sym);
  178. }
  179.  
  180. PUBLIC void hsh_delsym(HASH_TAB *tabp, void *isym)
  181. /****************************************************************************
  182. *
  183. * Function:        hsh_delsym
  184. * Parameters:    tabp    - The hash table
  185. *                isym    - Symbol to delete
  186. *
  187. * Description:    Removes a symbol from the hash table. "sym" is a pointer
  188. *                from a previous findsym() call. It points initially at the
  189. *                user space, but is decremented to get at the BUCKET header.
  190. *
  191. ****************************************************************************/
  192. {
  193.     HSH_BUCKET    *sym = HSH_HEADER(isym);
  194.  
  195.     if (tabp && sym) {
  196.         --tabp->numsyms;
  197.  
  198.         if ( (*(sym->prev) = sym->next) != NULL)
  199.             sym->next->prev = sym->prev;
  200.         }
  201. }
  202.  
  203. PUBLIC void *hsh_findsym(HASH_TAB *tabp, void *sym)
  204. /****************************************************************************
  205. *
  206. * Function:        hsh_findsym
  207. * Parameters:    tabp    - The hash table
  208. *                isym    - Symbol to look for
  209. * Returns:        pointer to the symbol if it exist, NULL otherwise
  210. *
  211. * Description:    Returns a pointer to the hash table element having a
  212. *                particular symbol, or NULL if the symbol isn't in the table.
  213. *
  214. ****************************************************************************/
  215. {
  216.     HSH_BUCKET *p;
  217.  
  218.     if (!tabp)            /* Table empty */
  219.         return NULL;
  220.  
  221.     p = (tabp->table)[ (*tabp->hash)(sym) % tabp->size ];
  222.  
  223.     while (p && (*tabp->cmp)(sym,HSH_USERSPACE(p)) )
  224.         p = p->next;
  225.  
  226.     return (p ? HSH_USERSPACE(p) : NULL);
  227. }
  228.  
  229. PUBLIC void *hsh_nextsym(HASH_TAB *tabp,void *i_last)
  230. /****************************************************************************
  231. *
  232. * Function:        hsh_nextsym
  233. * Parameters:    tabp    - The hash table
  234. *                i_last    - The last symbol accessed
  235. * Returns:        Pointer to the next symbol in the current chain
  236. *
  237. * Description:    Returns a pointer to the next node in the current chain that
  238. *                has the same key as the last node found (or NULL if there
  239. *                is no such node). "i_last" is a pointer returned from a
  240. *                previous findsym() or nextsym() call.
  241. *
  242. ****************************************************************************/
  243. {
  244.     HSH_BUCKET    *last = HSH_HEADER(i_last);
  245.  
  246.     for (; last->next; last = last->next)
  247.         if ( (tabp->cmp)(i_last, last->next + 1) == 0)    /* Keys match */
  248.             return HSH_USERSPACE(last->next);
  249.     return NULL;
  250. }
  251.  
  252. PRIVATE int (*User_cmp)(void *,void *);
  253.  
  254. PRIVATE int internal_cmp(HSH_BUCKET **p1,HSH_BUCKET **p2)
  255. {
  256.     return (*User_cmp)(HSH_USERSPACE(*p1),HSH_USERSPACE(*p2));
  257. }
  258.  
  259. PUBLIC int hsh_ptab(HASH_TAB *tabp,void (*print)(void *,void *),void *param,
  260.                 int sort)
  261. /****************************************************************************
  262. *
  263. * Function:        hsh_ptab
  264. * Parameters:    tabp    - The hash table
  265. *                print    - Routine to printe a symbol
  266. *                param    - Parameters to the print routine
  267. *                sort    - True if the table should be sorted
  268. * Returns:        True if completed, false otherwise
  269. *
  270. * Description:    Prints the table of symbols by calling the print routine
  271. *                for every symbol in the table. If sort is true, the table
  272. *                is sorted first before it is printed. The print function
  273. *                is called with two arguments:
  274. *
  275. *                    (*print)(sym,param)
  276. *
  277. *                Sym is a pointer to a HSH_BUCKET user area.
  278. *
  279. ****************************************************************************/
  280. {
  281.     HSH_BUCKET    **outtab,**outp,*sym,**symtab;
  282.     int            i;
  283.  
  284.     if (!tabp || tabp->size == 0)        /* table is empty */
  285.         return 1;
  286.  
  287.     if (!sort) {
  288.         for (symtab = tabp->table, i = tabp->size; --i >= 0 ; symtab++) {
  289.  
  290.             /* Print all symbols in the current chain. */
  291.  
  292.             for (sym = *symtab; sym ; sym = sym->next)
  293.                 (*print)(HSH_USERSPACE(sym),param);
  294.             }
  295.         }
  296.     else {
  297.         /* Allocate memory for the outtab, an array of pointers to
  298.          * HSH_BUCKETS, and initialise it. The outtab is different from
  299.          * the actual hash table in that every outtab element points
  300.          * to a single HSH_BUCKET structure, rather than to a linked list
  301.          * of them.
  302.          */
  303.  
  304.         if ( !(outtab = (HSH_BUCKET**)malloc(tabp->numsyms * sizeof(HSH_BUCKET*)) ))
  305.             return 0;
  306.  
  307.         outp = outtab;
  308.  
  309.         for ( symtab = tabp->table, i = tabp->size; --i >= 0; symtab++)
  310.             for (sym = *symtab; sym ; sym = sym->next) {
  311.                 if (outp > outtab + tabp->numsyms) {
  312.                     fprintf(stderr,"Internal error [ptab], table overflow\n");
  313.                     exit(1);
  314.                     }
  315.                 *outp++ = sym;
  316.                 }
  317.  
  318.         /* Sort the outtab and then print it. The (*outp) + 1 in the
  319.          * print call increments the pointer past the header part
  320.          * of the HSH_BUCKET structure. During sorting, the increment
  321.          * is done in internal_cmp.
  322.          */
  323.  
  324.         User_cmp = tabp->cmp;
  325.         assort((void**)outtab, tabp->numsyms, sizeof(HSH_BUCKET*), internal_cmp);
  326.  
  327.         for (outp = outtab, i = tabp->numsyms; --i >= 0; outp++)
  328.             (*print)(HSH_USERSPACE(*outp),param);
  329.  
  330.         free(outtab);
  331.         }
  332.     return 1;
  333. }
  334.